"""
题目：用递归求一个不含重复元素的数组的所有全排列（如 [1,2] 的全排列为 [[1,2],[2,1]]）

"""

def permute(nums):
    """递归求数组的所有全排列"""
    # 基线条件：空数组的全排列是包含空列表的列表
    if len(nums) == 0:
        #当输入数组 nums 为空时，返回 [[]]（空数组的全排列只有 “空列表” 这一种情况，用列表包裹空列表是为了保持递归返回值的结构一致性）。
        return [[]]
    result = []
    # 遍历每个元素，将其作为第一个元素，递归求剩余元素的全排列
    #循环变量 i 遍历数组的每个索引，依次将 nums[i] 作为全排列的第一个元素。
    for i in range(len(nums)):
        # 当前元素
        current = nums[i]
        # 剩余元素（排除当前元素） 即i前面的元素+i后面的元素
        remaining = nums[:i] + nums[i+1:]
        # 递归求剩余元素的全排列 对 remaining 数组递归调用 permute 函数，得到剩余元素的所有全排列
        # 思考：为什么这里可以用递归？
        # 回答：因为对n个元素进行全排列和n-1个元素进行全排列 要干的事情(逻辑)是一样的!
        for p in permute(remaining):
            # 将当前元素与剩余元素的全排列拼接
            #将当前元素 current 与剩余元素的某一种排列 p 拼接（例如 current=1，p=[2,3]，则拼接为 [1,2,3]），并将该排列加入 result 列表。
            #思考：为什么这里可以用递归？
            result.append([current] + p)
    return result
#算法逻辑总结：该递归算法的核心思想是：将全排列问题分解为 “选择第一个元素” + “求解剩余元素的全排列”。通过遍历每个元素作为 “第一个元素”，再递归处理剩余元素，最终拼接得到所有排列组合。
#这种方法的时间复杂度是O(n!)（n是数组长度，全排列的数量是(n!)
# 空间复杂度也是O(n!)（需要存储所有排列结果），是求解全排列的经典递归实现。

# 测试
if __name__ == "__main__":
    print(permute([1, 2, 3]))
    # 输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

    print(permute([])) # 输出：[[]]

    list1 = [1,2,3]
    list2 = [3,4,5,6]
    print(list1+list2) #[1, 2, 3, 3, 4, 5, 6]